package com.gorkr.labuladong.data_struct.array;

import org.junit.jupiter.api.Test;

import java.util.Calendar;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/08/08 22:27
 **/
public class M38ZiFuChuanDePaiLieIcofII {

    private List<String> res = new LinkedList<>();
    private char[] chars;

    public String[] permutation(String s) {
        chars = s.toCharArray();
        dfs(0);
        return res.toArray(new String[0]);

    }

    private void dfs(int x){

        if(x==chars.length-1){
            res.add(String.valueOf(chars));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        // 这里!!!!!
        for (int i = x; i < chars.length; i++) {
            if(set.contains(chars[i])){
                continue;
            }
            set.add(chars[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);

        }


    }

    void swap(int a, int b) {
        char tmp = chars[a];
        chars[a] = chars[b];
        chars[b] = tmp;
    }


    @Test
    public void test() {
        String[] abcs = permutation("aab");
        for (String s: abcs
        ) {
            System.out.println(s);
        }

    }



}
    